1038B - Non-Coprime Partition - CodeForces Solution


constructive algorithms math *1100

Please click on ads to support us..

Python Code:

import math
n=int(input())

if n == 1 or n == 2:
    print("No")
else:
    print("Yes")
    l1=[];l2=[]
    
    if n%2 == 0:
        l1.append(1);
        l1.append(n);
        
        for item in range(2,n):
            l2.append(item)
    else:
        l1.append(math.ceil(n/2))
        for item in range(1,n+1):
            if l1[0]!=item:
                l2.append(item)
    
    print(len(l1),end=" ")
    for item in l1:
        print(item,end=" ")
    print()
    print(len(l2),end=" ")
    for item in l2:
        print(item,end=" ")
    print()

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
int main()
{
    int n,target=-1;
    cin>>n;
    ll x=(n*(n+1))/2;
    for(ll i=2;i<=n;i++)
    {
        if(__gcd(i,x-i)>1)
        {
            target=i;
            break;
        }
    }
    if(target==-1)
    cout<<" No";
    else
    {
        cout<<" Yes\n";
        cout<<n-1<<" ";
        for(int i=1;i<=n;i++)
        {
            if(i!=target)
            cout<<i<<" ";
        }
        cout<<"\n";
        cout<<1<<" "<<target;
    }

}


Comments

Submit
0 Comments
More Questions

1654A - Maximum Cake Tastiness
1649A - Game
139A - Petr and Book
1612A - Distance
520A - Pangram
124A - The number of positions
1041A - Heist
901A - Hashing Trees
1283A - Minutes Before the New Year
1654D - Potion Brewing Class
1107B - Digital root
25A - IQ test
785A - Anton and Polyhedrons
1542B - Plus and Multiply
306A - Candies
1651C - Fault-tolerant Network
870A - Search for Pretty Integers
1174A - Ehab Fails to Be Thanos
1169A - Circle Metro
780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)
1151B - Dima and a Bad XOR
1435B - A New Technique
1633A - Div 7